\chapter{Number Theory}

\section{Modular Arithmetic}
	\kactlimport{Modular Arithmetic/ModIntShort.h}
	\kactlimport{Modular Arithmetic/ModFact.h}
	\kactlimport{Modular Arithmetic/ModMulLL.h}
	\kactlimport{Modular Arithmetic/FastMod.h}
	\kactlimport{Modular Arithmetic/ModSqrt.h}
	\kactlimport{Modular Arithmetic/ModSum.h}

\section{Primality}
	\subsection{Primes}
	$p=962592769$ is such that $2^{21} \mid p-1$, which may be useful. For hashing
	use 970592641 (31-bit number), 31443539979727 (45-bit), 3006703054056749
	(52-bit). There are 78498 primes less than 1\,000\,000.

	Primitive roots exist modulo any prime power $p^a$, except for $p = 2, a > 2$, and there are $\phi(\phi(p^a))$ many.
	For $p = 2, a > 2$, the group $\mathbb Z_{2^a}^\times$ is instead isomorphic to $\mathbb Z_2 \times \mathbb Z_{2^{a-2}}$.

	\subsection{Divisors}
	$\sum_{d|n} d = O(n \log \log n)$.

	The number of divisors of $n$ is at most around 100 for $n < 5e4$, 500 for $n < 1e7$, 2000 for $n < 1e10$, 200\,000 for $n < 1e19$.

	\textbf{Dirichlet Convolution:} Given a function $f(x)$, let 

	$(f*g)(x)=\sum_{d|x}g(d)f(x/d)$. 

	If the partial sums $s_{f*g}(n),s_g(n)$ can be computed in $O(1)$ and $s_f(1\ldots n^{2/3})$ can be computed in $O\left(n^{2/3}\right)$ then all $s_f\left(\frac{n}{d}\right)$ can as well. Use

	$$s_{f*g}(n)=\sum_{d=1}^ng(d)s_f(n/d).$$ 

	% \implies s_f(n)=\frac{s_{f*g}(n)-\sum_{d=2}^ng(d)s_f(n/d)}{g(1)}
	
    If $f(x)=\mu(x)$ then $g(x)=1, (f*g)(x)=(x == 1)$, and $s_f(n)=1-\sum_{i=2}^ns_f(n/i)$.

    If $f(x)=\phi(x)$ then $g(x)=1, (f*g)(x)=x$, and $s_f(n)=\frac{n(n+1)}{2}-\sum_{i=2}^ns_f(n/i).$

	% Nisiyama_Suzune tutorial:
	% https://codeforces.com/blog/entry/54150

	\begin{comment}
	Let $s(x)=\sum_{i=1}^x\phi(i).$ Then 
	$$s(n)=\frac{n(n+1)}{2}-\sum_{i=2}^ns\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
	can be computed in faster than $\Theta(n)$.
	\end{comment}
	
	\kactlimport{Primality/Sieve.h}
	\kactlimport{Primality/MultiplicativePrefixSums.h}
	\kactlimport{Primality/PrimeCnt.h}
	\kactlimport{Primality/MillerRabin.h}
	\kactlimport{Primality/FactorFast.h}

\section{Euclidean Algorithm}

\begin{comment}
	\subsection{Bézout's identity}
	For $a \neq $, $b \neq 0$, then $d=\gcd(a,b)$ is the smallest positive integer for which there are integer solutions to
	$$ax+by=d$$
	If $(x,y)$ is one solution, then all solutions are given by
	$$\left(x+\frac{kb}{\gcd(a,b)}, y-\frac{ka}{\gcd(a,b)}\right), \quad k\in\mathbb{Z}$$
\end{comment}

	\kactlimport{Euclid/FracInterval.h}
	\kactlimport{Euclid/Euclid.h}
	\kactlimport{Euclid/CRT.h}
	\kactlimport{Euclid/ModArith.h}
	
\section{Pythagorean Triples}
	 The Pythagorean triples are uniquely generated by
	 \[ a=k\cdot (m^{2}-n^{2}),\ \,b=k\cdot (2mn),\ \,c=k\cdot (m^{2}+n^{2}), \]
	 with $m > n > 0$, $k > 0$, $m \bot n$, and either $m$ or $n$ even.

\section{Lifting the Exponent}

For $n>0$, $p$ prime, and ints $x,y$ s.t. $p\nmid x,y$ and $p|x-y$:

% https://brilliant.org/wiki/lifting-the-exponent/

\begin{itemize}
\item $p\neq 2$ or $p=2, 4|x-y$ $\implies v_p(x^n - y^n) = v_p(x - y) + v_p(n)$.
\item $p=2, 2|n \implies v_2(x^n-y^n)=v_2((x^2)^{n/2}-(y^2)^{n/2})$.
\end{itemize}
